Статья 1114

Название статьи

ОЦЕНКИ НЕНАДЕЖНОСТИ СХЕМ В БАЗИСЕ РОССЕРА – ТУРКЕТТА

Авторы

Алехина Марина Анатольевна, доктор физико-математических наук, профессор, заведующая кафедрой дискретной математики, Пензенский государственный университет (Россия, г. Пенза, ул.Красная, 40), alehina@pnzgu.ru
Барсукова Оксана Юрьевна, старший преподаватель, кафедра дискретной математики, Пензенский государственный университет (Россия, г. Пенза, ул. Красная, 40), kuzya_7@mail.ru

Индекс УДК

519.718

Аннотация

Актуальность и цель. В современной математике и технике теория синтеза схем из ненадежных функциональных элементов занимает важное место. Стоит отметить, что до сих пор рассматривались задачи построения надежных схем, реализующих только булевые функции. В данной работе предложена математическая модель построения асимптотически оптимальных по надежности схем, реализующих функции трехзначной логики. Исследуется задача реализации функций трехзначной логики схемами из ненадежных функциональных элементов в базисе Россера – Туркетта. Предполагается, что все базисные элементы независимо друг от друга переходят в неисправные состояния и любой базисный элемент на любом входном наборе (с вероятностью 1 – 2ε) выдает правильное значение и с вероятностью, равной ε, может выдать любое из двух неправильных. Целью данной работы является получение нижних и верхних оценок ненадежности схем и построение асимптотически оптимальных по надежности схем.
Результаты. В результате исследования полученные ранее верхние оценки ненадежности удалось доказать, существенно ослабив ограничения на (ранее эта вероятность зависела от n – числа переменных функции, а в этой работе ее удалось заменить константой). Доказана асимптотическая точность верхних оценок, т.е. в базисе Россера – Туркетта найден класс K функций трехзначной логики такой, что при реализации любой функции из этого класса любой схемой нижняя оценка ненадежности этой схемы будет асимптотически равна верхней оценке ненадежности. Класс описан в явном виде, а также найдена оценка для количества функций, входящих в данный класс.
Выводы. Установлено, что любую функцию трехзначной логики можно реализовать схемой, функционирующей с ненадежностью, асимптотически (при ε → 0) не больше 6ε. Доказано, что функции класса K (содержащего почти все функции трехзначной логики) нельзя реализовать схемами с ненадежностью, асимптотически (при ε → 0) меньше 6ε. Таким образом, почти все функции трехзначной логики можно реализовать асимптотически оптимальными по надежности схемами, функционирующими с ненадежностью, асимптотически равной 6ε при ε → 0 .

Ключевые слова

функции трехзначной логики, схема из функциональных элементов, ненадежность схемы.

Скачать статью в формате PDF
Список литературы

1. Васин, А. В. О базисах, в которых асимптотически оптимальные схемы функ-ционируют с ненадежностью 5ε / А. В. Васин // Известия высших учебных заведе-ний. Поволжский регион. Физико-математические науки. – 2010. – № 1 (13). – С. 64–79.
2. Грабовская, С. М. О надежности неветвящихся программ с ненадежным опе-ратором условной остановки в произвольном полном конечном базисе /
С. М. Грабовская // Известия высших учебных заведений. Поволжский регион. Физико-математические науки. – 2011. – № 3 (19). – С. 52–60.
3. Алехина, М. А. О ненадежности схем, реализующих функции из P3/ М. А. Алехина, О. Ю. Барсукова // Известия высших учебных заведений. Поволж-ский регион. Физико-математические науки. – 2012. – № 1 (21). – С. 57–65.
4. Яблонский, С. В. Введение в дискретную математику / С. В. Яблонский. – М. : Наука, 1986. – 384 с.
5. Алехина, М. А. О ненадежности схем из ненадежных функциональных эле-ментов при однотипных константных неисправностях на выходах элементов / М. А. Алехина // Дискретная математика. – 1993. – Т. 5, № 2. – С. 59.
6. Alekhina, M.A. Synthesis and complexity of asymptotically optimal circuits with unreliable gates/M.A.Alekhina // Fundamenta Informaticae. – 2010. – № 104 (3). – P. 219–222.

 

Дата создания: 23.07.2014 11:34
Дата обновления: 23.07.2014 12:23